package videoCourse.sort;

import java.util.Arrays;

public class MyMergerSort {

    public static void main(String[] args) {
        int[] arr = new int[]{1,3,5,2,4,6,8,10};
        mergerSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));

    }
    private static void mergerSort(int[] arr,int start,int end){
        int mid = (start + end) /2;
        if(start < end){
            mergerSort(arr,start,mid);
            mergerSort(arr,mid+1,end);
            merger(arr,start,mid,end);
        }
    }

    private static void merger(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start +1];
        int i = start;
        int j = mid+1;
        int index = 0;
        while(i<=mid && j<=end){
            if(arr[i] <= arr[j]) {
                temp[index] = arr[i];
                i++;
            }else{
                temp[index] = arr[j];
                j++;
            }
            index++;
        }
        while(i<=mid){
            temp[index++] = arr[i++];
        }
        while (j<=end){
            temp[index++] = arr[j++];
        }

        for(int k = 0;k<temp.length;k++){
            arr[start+k] = temp[k];
        }
    }
}
